package com.leetcode.no25;

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {


        // 最后结果的头结点
        ListNode resultHead = head;

        // 首先获取最后的头结点 即第k个节点
        // 同时注意base case  即刚开始链表长度就小于k
        for (int i = 1; i <= k; i++) {
            resultHead = resultHead.next;
            if (resultHead == null) {
                return head;
            }
        }

        Deque<ListNode> deque = new LinkedList<ListNode>();

        // 用来遍历的结点
        ListNode tmpNode = head;

        //
        ListNode tmpHead, tmpTail;

        boolean isLast = false;

        while (tmpNode != null) {
            // 放入栈中
            for (int i = 1; i <= k; i++) {
                // 说明到末尾部分, 且该部分结点数量小于k 此部分保持原状就行
                if (tmpNode == null) {
                    isLast = true;
                    break;
                }

                deque.push(tmpNode);
                tmpNode = tmpNode.next;
            }

            if (isLast) {
                break;
            }

            // 每组内 头尾 的交换
            tmpHead = deque.getFirst();

            // 注意，这里用的是poll
            tmpTail = deque.pollLast();

            tmpHead.next = tmpTail.next;

            // 组内 每个结点开始 调换顺序
            while (!deque.isEmpty()) {
                tmpTail.next = deque.pollLast();
                tmpTail = tmpTail.next;
            }
        }

        return resultHead;
    }

    public ListNode reverseKGroup01(ListNode head, int k) {
        Deque<ListNode> deque = new LinkedList<>();
        ListNode resultHead, tmpNode;
        resultHead = new ListNode(0);
        tmpNode = resultHead;

        while (true) {
            int count = 0;
            ListNode tmp = head;

            while (tmp != null && count < k) {
                deque.offer(tmp);
                tmp = tmp.next;
                count++;
            }

            if (count != k) {
                tmpNode.next = head;
                break;
            }

            while (!deque.isEmpty()) {
                tmpNode.next = deque.pollLast();
                tmpNode = tmpNode.next;
            }
            tmpNode.next = tmp;
            head = tmp;
        }

        return resultHead.next;
    }

    public ListNode reverseKGroup02(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) end = end.next;
            if (end == null) break;
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;

            end = pre;
        }
        return dummy.next;
    }

    public ListNode reverseKGroup03(ListNode head, int k) {
        ListNode dummy = new ListNode(0), prev = dummy, curr = head, next;
        dummy.next = head;
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        head = dummy.next;
        for (int i = 0; i < length / k; i++) {
            for (int j = 0; j < k - 1; j++) {
                next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
            curr = prev.next;
        }
        return dummy.next;
    }

    // 翻转一段链表
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    // 测试结果
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode tmpNode = head;

        int[] arr = {1, 2, 3, 4, 5};
        for (int num : arr) {
            tmpNode.val = num;

            if (num == 5) break;
            tmpNode.next = new ListNode();
            tmpNode = tmpNode.next;
        }
        tmpNode = head;

        while (tmpNode != null) {
            System.out.print(tmpNode.val);
            tmpNode = tmpNode.next;
        }

        Solution s1 = new Solution();


        head = s1.reverseKGroup(head, 2);
        //  tmpNode = head;

        while (head != null) {
            System.out.print(head.val);
            head = head.next;
        }

    }
}




